package dp;

public class PerfectSquares {

	public static void main(String[] args) {
		PerfectSquares perfectSquares = new PerfectSquares();
		perfectSquares.numSquares(5);
	}
	public int numSquares(int n) {
		if (n <= 0) {
			return 0;
		}
		// 这道题有点类似于换零钱，只不过货币的种类不是固定的
		int k = (int) Math.sqrt(n);
		int[] money = new int[k];
		for (int i = 0; i < k; i++) {
			money[i] = (i + 1) * (i + 1);
		}
		for (int i : money) {
			System.out.println(" money: " + i);
		}
		// res[i][j] 表示使用0...i种货币构成n元钱的最少货币数
		int[][] res = new int[k][n + 1];
		for (int j = 0; j <= n; j++) {
			// 由于我们知道第一种货币是1，所以所有的j都是可以构成的
			res[0][j] = j;
		}
		int temp = Integer.MAX_VALUE;
		for (int i = 1; i < k; i++) {
			for (int j = 1; j <= n; j++) {
				temp = Integer.MAX_VALUE;
				if (j >= money[i]) {
					temp = res[i][j - money[i]] + 1;
				}
				res[i][j] = Math.min(res[i - 1][j], temp);
			}
		}
		for (int i = 0; i < k; i++) {
			for (int j = 0; j <= n; j++) {
				System.out.print(res[i][j] + " ");
			}
			System.out.println();
		}
		return res[k - 1][n];
	}
}
